//: [Previous](@previous)
/*:
 
 #69 [Sqrt(x)](https://leetcode.com/problems/sqrtx/description/)
 
 Implement `int sqrt(int x)`.
 
 Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
 
 Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
 
 Example 1:
 ```
 Input: 4
 Output: 2
 ```
 
 Example 2:
 ```
 Input: 8
 Output: 2
 Explanation: The square root of 8 is 2.82842..., and since
              the decimal part is truncated, 2 is returned.
 ```
 */
import Foundation

class Solution {
    func mySqrt(_ x: Int) -> Int {
        
        if x <= 1 {
            return x
        }
        
        var left = 2, right = x / 2
        
        while left <= right {
            let mid = (left + right) / 2
            if x / mid > mid {
                left = mid + 1
            } else if x / mid == mid {
                return mid
            } else {
                right = mid - 1
            }
        }
        return right
    }
}

print(Solution().mySqrt(4))
print(Solution().mySqrt(8))

//: [Next](@next)
